The Programmer Disk/The Programmer Disk (Microforum).iso/xpro/c/pro12/hsort.c

C/C++ Source or Header | 1991-03-31 | 5.6 KB | 224 lines

/***********************************************************************/
/*  SORT(): Non-Recursive Heap Sort function.                          */
/*  See the function declaration for calling information.              */
/* Function is by Bruce Feist; please contact me on CompuServe with    */
/*    a message on BPROGB, MACDEV, or EASYPLEX if you have any         */
/*    questions or problems.                                           */
/* You can also reach me at the Enlightened Board, at [phone],  */
/*   N/8/1                                                             */
/* Feel free to make use of this code in your own programs.            */
/***********************************************************************/

#define VERBOSE (0)

#include <process.h>
#include <alloc.h>
#include <stdlib.h>
#include <mem.h>
#include <stddef.h>
#include <stdio.h>

#include "sort.h"

static void build_heap (void), extract_heap (void);
static void heapify (int, int);

static void show_node (int);
#if VERBOSE
static void show_heap (void);
#endif

/* heapsort uses an array of pointers as its data structure to   */
/* represent the heap.                                           */
/* Children of slot i are slots 2i+1 and 2i+2.                   */

/* Note:  as an alternative, we could have made the input array */
/* into a heap (instead of messing with the pointers.           */

static char *base, *temp_record;
static int nelem, width, (*compare)(void *, void *);

int
hsort (void *pbase, size_t pnelem, size_t pwidth, int pcompare())

{
  base = pbase;
  nelem = pnelem;
  width = pwidth;
  compare = pcompare;
  if ((temp_record = malloc (pwidth)) == NULL)
    return S_NOMEM;

#if VERBOSE
  printf ("Sort (base = %p, n = %u, w = %u)\n", base, nelem, width);
#endif

  build_heap ();
  extract_heap ();

  free (temp_record);

  return S_OK;
  } /* end hsort */


void
build_heap()

{
  register int left;
  register char *left_ptr;
  int right;

#if VERBOSE
  puts ("Building heap. . .\n");
#endif

  right = nelem - 1;
  for (left = (nelem >> 1) - 1, left_ptr = base + width * left;
       1; /* keep going until the 'break' */
       left--, left_ptr -= width)
  {
#if VERBOSE
    printf ("temp <- %d to start heapification.\n", left);
#endif
    memcpy (temp_record, left_ptr, width);
    heapify (left, right);
    if (! left)
      break;
    }

  } /* end build_heap */


void
extract_heap ()
{
  register int right;
  register char *right_ptr;

#if VERBOSE
  puts ("Extracting from heap. . .\n");
#endif

  for (right = nelem - 1, right_ptr = base + width * right;
       1; /* continue until the 'break' */
       right_ptr -= width)
  {
    memcpy (temp_record, right_ptr, width);
    memcpy (right_ptr,   base,      width);
#if VERBOSE
    printf ("temp <- %d to start extract\n", right);
    printf ("%d <- %d to start extract\n", right, 0);
    printf ("Returning %lf\n", ((double *) base) [right]);
#endif
    if (! --right)
      break;
    heapify (0, right);
    }
#if VERBOSE
  printf ("%d <- temp to finish extract\n", 0);
#endif
  memcpy (base, temp_record, width);
  } /* end extract_heap */


/* When heapify is called, (left+1,right) is already heapified and       */
/* temp_record contains what we'd like to add to it to make (left,right) */
/* a heap.                                                               */
/*   So, we look for the first descendent of 'left' that's bigger than   */
/* it.  All of its ancestors move up a generation, and temp_record       */
/* becomes its parent.                                                   */

void
heapify (int left, int right)

{
  register int  child;
  register char *ptr_child;
  char          *ptr_child2, *ptr_parent;

  child = left;
  ptr_child = base + child * width;

#if VERBOSE
  show_heap();
  printf ("Heapifying from %d to %d.\n", left, right);
#endif

  while (1) /* continue until the 'break' */
  {
    child <<= 1;
    child++;
    ptr_parent = ptr_child;

    if (child > right)  /* if parent was a leaf, replace with temp_record */
    {
#if VERBOSE
      printf ("%d <- temp since %d is leaf.\n", parent, parent);
#endif
      memcpy (ptr_parent, temp_record, width);
      break;
      } /* end if */

    ptr_child = base + child * width;
    if (child < right)  /* Is there more than one child? */
    {
      /* Use the biggest child. */
      if (compare (ptr_child, ptr_child2 = ptr_child + width) < 0)
      {
        child++;
        ptr_child = ptr_child2;
        }  /* end if ptr_child < ptr_child2 */
      } /* end if child < right */

    if (compare (temp_record, ptr_child) >= 0)  /* Is temp_record bigger? */
    {
#if VERBOSE
      printf ("%d <- temp since temp is bigger than %d.\n", parent, child1);
#endif
      memcpy (ptr_parent, temp_record, width);
      break;
      }

#if VERBOSE
    printf ("%d <- %d since we're not done yet\n", parent, child1);
#endif
    memcpy (ptr_parent, ptr_child, width);      /* Promote by a generation */
    }  /* end while TRUE */

#if VERBOSE
  puts ("Done heapifying.");
  show_heap();
#endif
  } /* end heapify */


void
show_heap ()
{
  puts ("The heap:");
  show_node (0);
  }

void
show_node (int node_id)
{
  int child1, child2, ancestor;

  child1 = node_id * 2 + 1;
  child2 = child1 + 1;

  printf ("%.4lf\t", ((double *) base) [node_id]);
  if (child1 < nelem)
    show_node (child1);
  else
     putchar ('\n');

  if (child2 < nelem)
  {
    for (ancestor = 1; ancestor < child2; ancestor <<= 1)
      putchar ('\t');
    show_node (child2);
    }
  } /* end show_node */